1. Field of the Invention
The present invention relates to a frame multiplexing device that multiplexes frames of variable length.
2. Description of the Related Art
Conventionally, a frame multiplexer is proposed as a communication device that multiplexes traffic input into the frame multiplexer such as Ethernet (registered trademark) frames (or packets) of variable length. When a total input rate becomes higher than an output rate of the frame multiplexer, congestion occurs and frames are discarded.
To prevent frames in traffic of a line having a narrow bandwidth from being discarded due to a line having a wide bandwidth, a function of multiplexing frames in traffic of the lines is necessary so that each of the lines has an equal output rate. A frame multiplexer using a queue buffer retrieving control with weighted round robin (WRR) is proposed as a frame multiplexer having such function.
FIG. 8 is a block diagram of a conventional frame multiplexer using the queue-buffer retrieving control with WRR. As shown in FIG. 8, a frame multiplexer 1 includes plural queue buffers #1 to #n (2a, 2b, 2c, 2d) and a scheduler 3. Each of the queue buffers 2a, 2b, 2c, 2d is provided for each of lines, and temporarily stores frames input from each of the lines into the frame multiplexer 1.
The scheduler 3 cyclically determines a retrieving order to retrieve a frame in each of the queue buffers 2a, 2b, 2c, 2d, so that an output rate of the frame multiplexer 1 corresponds to a weight assigned to each line. The scheduler 3 ignores a line corresponding to a queue buffer 2a, 2b, 2c, 2d in which no frame is stored. Therefore, it is possible to multiplex traffic of each line so that an output rate of each line becomes equal, by assigning the same weight to each line.
A bandwidth guarantee device for logic channels in physical lines including plural channels in which traffic flows generated by individual users are input is also proposed. The bandwidth guarantee device includes a scheduler that performs unbiased bandwidth division for each traffic flow, and a shaper that assigns a bandwidth to limit a rate of each channel without exceeding a bandwidth that is provided for each channel (for example, Japanese Patent Laid-open Publication No. 2000-49812). The shaper uses WRR when frames are transmitted from each channel buffer to an output buffer of the device.
However, the conventional frame multiplexer described above has following problems. Generally, a queue buffer is realized by a shared memory in view of achieving high memory utilization efficiency. Therefore, it is required to retrieve an empty address when writing a frame in the shared memory, and to release a used address when reading a frame in the shared memory. To manage such empty address of the shared memory, it is necessary to prepare a managing memory with an enough capacity to store a data amount corresponding to the number of addresses in the shared memory multiplied by address length.
The frame stored in the queue buffer is written on an arbitrary address in the shared memory. To manage an address of each frame on the memory, and an order thereof, it is necessary to prepare a managing memory with an enough capacity to store a data amount corresponding to queue buffer length multiplied by address length.
When the queue buffer retrieving control with WRR is employed in the best effort service that utilizes the maximum output rate of the frame multiplexer, frames are output without an unnecessary interval. Therefore, a time T0 that is necessary to read the shortest frame is equal to X0 divided by Y0, where X0 is length of the shortest frame of variable-length, and Y0 is an output rate of the frame multiplexer. Therefore, after determining to retrieve the shortest frame, the scheduler needs to determine the next frame to be retrieved within the time T0.
Therefore, the two managing memories described above are realized by an expensive synchronized random access memory (SRAM) to access the two memories within such a short time. The larger number of lines accommodated in the frame multiplexer leads to higher cost. A required capacity of the memory increases as the number of the accommodated lines increases, and therefore, requires a large SRAM. This leads to an increase in size of the frame multiplexer. Therefore, the number of the accommodated lines is disadvantageously limited even when more accommodated lines are desired. Moreover, the time T0 becomes shorter as an output speed of the frame multiplexer increases, and it becomes necessary to determine which frame is to be retrieved next within less time. Therefore, the output speed is limited even when the higher output speed is desired.
In addition, with the conventional device described above, high processing speed cannot be achieved because the device needs software to perform such complicated algorithm as multiplication and division. If the high speed processing is impossible, longer intervals are required for executing a control for allowing the plural lines to equally utilize the output bandwidth of the frame multiplexer. This leads to degradation of accuracy in equal division.